/**
 * 
 */

/**
 * @author 
 * Yannic Remmet			196983
 * Tobias Trabelsi			197112
 * Anna-Katharina Wickert	197122
 */
public class SearchTree<T extends Comparable<T> > extends BinaryTree<T> {
	SearchTree() {
		super();
	}
	SearchTree(TreeNode<T> t){
		super(t);
	}
	public boolean insert(T o){
		if (test)
			System.out.println("in inser(T o) : getRoot: " + getRoot());
		return insert(o, getRoot());
	}
	
	private boolean insert(T o, TreeNode<T> t){
		if (test) 
			System.out.println("Beginning of insert(o, t): t.getKey: " + t.getKey() + " o: " + o + " t.getRight() " + t.getRight() + " t.getLeft() " + t.getLeft());
		/*if (t.getKey() == null) {
			t.setKey(o);
			return true;
		} */
		if (o == null)
			return false;
		if (test) {
			System.out.print("t.getKey() == o : ");  System.out.println(t.getKey() == o);
		}
		if (t.getKey() == o) {
			if (test)
				System.out.println("in if t.getKey() == o");
			return false; 
		}
		if (test){
			System.out.println("before if - else (rekursive) t.getRight(): " + t.getRight() + " t.getLeft() " + t.getLeft() + " t.getKey() " + t.getKey() + " o: " + o + " t.getKey().compareTo(o) " + t.getKey().compareTo(o));
			if (testdetails){
				System.out.println("t.getRight: " + t.getRight());
				System.out.println("t.getLeft: " + t.getLeft());
				System.out.println("t.getKey: " + t.getKey());
				System.out.println("o: " + o);
				System.out.println("t.getKey().compareTo(o) " + t.getKey().compareTo(o));
			}
		}
		if (t.getKey().compareTo(o) > 0){
			if (test){
				if (testdetails){
					System.out.println(("t.getRight(): " + t.getRight()));
					System.out.println("o: " + o);
				}
				System.out.println("in if t.getRight(): " + t.getRight() + " o: " + o);
			}
			if (t.getRight() == null){
				if (test)
					System.out.println("in t.getRight()  == null");
				TreeNode<T> res = new TreeNode<T>(o);
				t.setRight(res);
				return true;
			}
			else {
				return insert(o, t.getRight());	
			}
		}
		else {
			if (test)
				System.out.println("in else t.getLeft(): " + t.getLeft() + " o: " + o);
			if( t.getLeft() == null){
				if (test)
					System.out.println("in t.getLeft() == null");
				TreeNode<T> res = new TreeNode<T>(o);
				t.setLeft(res);
				return true;
			}
			else {
				return insert(o, t.getLeft());	
			}
		}

	}
	
	boolean test = false;
	boolean testdetails = false;
}
